package com.zp.self.module.level_4_算法练习.算法.位图;
import org.junit.Test;

/**
 * @author By ZengPeng
 */
public class 力扣_953_验证外星语词典 {
    @Test
    public void main() {
        
        Solution solution = new 力扣_953_验证外星语词典().new Solution();
        System.out.println(solution.isAlienSorted(new String[]{"apple","app"},"abcdefghijklmnopqrstuvwxyz"));
    }

    /**
     题目：某种外星语也使用英文小写字母，但可能顺序 order 不同。字母表的顺序（order）是一些小写字母的排列。
         给定一组用外星语书写的单词 words，以及其字母表的顺序 order，只有当给定的单词在这种外星语中按字典序排列时，返回 true；否则，返回 false。

         示例 1：
         输入：words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
         输出：true
         解释：在该语言的字母表中，'h' 位于 'l' 之前，所以单词序列是按字典序排列的。

         示例 2：
         输入：words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
         输出：false
         解释：在该语言的字母表中，'d' 位于 'l' 之后，那么 words[0] > words[1]，因此单词序列不是按字典序排列的。

         示例 3：
         输入：words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
         输出：false
         解释：当前三个字符 "app" 匹配时，第二个字符串相对短一些，然后根据词典编纂规则 "apple" > "app"，
         因为 'l' > '∅'，其中 '∅' 是空白字符，定义为比任何其他字符都小（更多信息）。


     分析：【P 💖💖】
        1.位图+排序：记录每个字母顺序，排序比较时传入比较器，得出对比值,升序
                    --执行耗时:0 ms,击败了100.00% 的Java用户
                    --编码耗时:[25:28]

     边界值 & 注意点：
        1.
     **/
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public boolean isAlienSorted(String[] words, String order) {
        int[] arr = new int[123];
        char[] chars = order.toCharArray();
        for (int i = 0; i < chars.length; i++)
            arr[chars[i]] = i;
        for(int i = 1; i < words.length; i++) {
            char[] pro = words[i-1].toCharArray();
            char[] current = words[i].toCharArray();
            int j= 0,pl=pro.length,cl = current.length;
            while (j<pl && j<cl){
                //前面的大，直接返回
                if(arr[pro[j]]>arr[current[j]])
                    return false;
                else if(arr[pro[j]]<arr[current[j]]){
                    break;
                }
                j++;
            }
            //判断是否包含的情况
            if(cl==j && pl>cl)
                return false;
        }
        return true;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}